1. Field of the Inventions
The invention relates generally to encryption for storage and specifically to the use of block ciphers in modified counter mode for encrypted storage.
2. Background Information
A symmetric cipher is an encryption system which uses the same key for encrypting and decrypting messages. Therefore, the encrypting party and the decrypting party have to share this key. A message that is to be encrypted is known as a plaintext message and once the message is encrypted it is referred to as a ciphertext message. In particular, a block cipher encrypts a fix size plaintext message into a fixed size ciphertext message. Typically the size of the plaintext and ciphertext are the same referred to as the block size. In the operation of a block cipher, the same plaintext yields the same ciphertext when encrypted with the same key.
FIG. 1 illustrates a typical block cipher. Plaintext (P) 102 is fed into block cipher 104 and an encryption function (EK) based on key K is applied to plaintext 102 resulting in ciphertext (C) 106, i.e., C=EK(P). Decryption involve using block cipher 108 which applies a corresponding decryption function (DK) also based on key K, i.e., P=DK(C).
There are many block ciphers in use today, such as Advanced Encryption Standard (AES), blowfish, twofish, Data Encryption Standard (DES), triple-DES, International Data Encryption Algorithm (IDEA), RC6 (RC variants has a has a long and ambiguous history some attribute it to mean “Rivest Cipher” or “Ron's Code.) These block ciphers commonly have block sizes of 64, 128, 192 and 256 bits. However, typically, a message longer than many block sizes need to be encrypted. Several strategies are used to encrypt long messages.
The most straightforward of these strategies is known as electronic codebook (ECB) mode. FIG. 2A illustrates how plaintext message 212 is encrypted using ECB mode. Plaintext message 212 is broken up into plaintext blocks 202a, 202b, 202c, etc, of the block size of the block cipher. Each block is encrypted using block cipher 104 to produce ciphertext blocks 206a, 206b, 206c, etc. Block cipher 104 can be implemented with a single cipher or multiple copies of the single cipher in a parallel fashion. Typically, it is a single cipher unless a high degree of parallelism is desired. Ciphertext blocks 206a, 206b, 206c, etc can be assembled into ciphertext message 216.
FIG. 2B illustrates the decryption of ciphertext message 216 using ECB mode. Block cipher 108 is used to decode blockwise the constituent ciphertext blocks 206a, 206b, 206c, etc, into plaintext blocks 202a, 202b, 202c which can be assembled into plaintext message 212. Mathematically, encryption follows Ci=EK(Pi) and decryption follows Pi=DK(Ci).
ECB mode is typically adapted to blocks of data and while applicable to streams, there was a need to use other approaches to strengthen encryption in a stream context. Several approaches to convert the block cipher into a stream cipher are commonly used. Two general approaches are chaining modes and feedback modes. For the remaining figures, the breaking apart of messages into blocks and the assembling of blocks into a message is omitted for clarity. Furthermore, for the sake of example, only three stages of encryption are shown. It should be understood that an arbitrary number of stages may be present.
Chaining modes typically use the ciphertext generated in previous encryption blocks and combine them with the plaintext prior to encryption. FIG. 3 illustrates the encryption and decryption of using cipher-block chaining (CBC) mode. In essence to encrypt, the previous ciphertext block is XORed to the plaintext block. For example as shown in encryption system 300, ciphertext block 306a is XORed with plaintext block 202b before applying block cipher 104 to produce ciphertext block 306b. The process begins with initialization vector 302 which is typically a random block shared between the encrypting party and the decrypting party. The corresponding decryption is illustrated by system 350. The encryption is defined by Ci=EK(Pi⊕Ei−1) and the decryption by Pi=DK(Ci)⊕Ci−1.
Another example of chaining mode is propagating cipher-block chaining (PCBC) mode. This is similar to CBC mode except that the previous plaintext block is also XORed with the previous ciphertext block and the plaintext block. Mathematically, the encryption is defined by Ci=EK(Pi⊕Pi−1⊕Ci−1) and the decryption by Pi=DK(Ci)⊕Ci−1⊕Pi−1.
Feedback modes utilize only the encryption portion of block cipher and are often employed to minimize the complexity of the encryption. Additionally, it enables the use of one-way ciphers which can encrypt efficiently but not decrypt efficiently. FIG. 4 illustrates the cipher feedback mode (CFB). In this mode, the previous ciphertext block is encrypted and XORed with the current plaintext block to produce a new ciphertext block. For example as shown in encryption system 400, ciphertext block 406a is encrypted and XORed with plaintext block 202b to produce ciphertext block 406b. Again an initialization vector (402) is used to start the process. Decryption is shown in system 450. Mathematically, the encryption is defined by Ci=Pi⊕EK(Ci−1) and the decryption by Pi=Ci⊕EK(Ci−1). It should be noted that block cipher decryption is not used in decryption and that the decryption and encryption are nearly identical.
Another noteworthy feedback mode is output feedback (OFB) mode. In this mode, the output block produced by the block cipher encryption is supplied to the input block of the next block cipher. The ciphertext block is generated by XORing the plaintext block with the output block. Mathematically, the encryption is defined by Ci=Pi⊕Oi and the decryption by Pi=Ci⊕Oi, where Oi=EK(Oi−1). It should be noted that structurally, the same configuration for encryption can be used for decryption.
In addition to chaining mode and feedback mode, one other mode of using block cipher is counter (CTR) mode. CTR mode is inspired by the one-time pad cipher which basically calls for a random block being XORed with the plaintext to generate ciphertext. However, one-time pad ciphers are impractical. So rather than randomly select the blocks, a sequence of known blocks, T0, T1, T2, . . . is encrypted to produce a cryptographically unpredictable sequences of one-time pads, EK(T0), EK(T1), EK(T2), . . . . In keeping with convention the known blocks T0, T1, T2, . . . will be referred to as counter blocks even though as is discussed below, they need not be counters.
FIG. 5A shows CTR mode encryption system 500. For example, ciphertext block 506b is created by XORing plaintext block 202b with the result by block cipher 104 of encrypting “counter” block 502b. Mathematically, the encryption is defined by Ci=Pi⊕EK(Ti). Likewise, FIG. 5B shows the corresponding CTR mode decryption system 550. Specifically, ciphertext block 506a can be deciphered by XORing the ciphertext block 506a with the result of block cipher 104 of encrypting counter block 502a to recover plaintext block 202a. Mathematically, the decryption is defined by Pi=Ci⊕EK(Ti).
FIG. 5C shows a common form of the “counter” used in CTR mode. Counter block 502 comprises nonce 520 and counter 522. Nonce 520 is a one-time random number which is shared between the encrypting party and the decrypting party. Counter 522 is a counter of bit length less than the block size of the counter block. The next result of this construction of a counter block is that Ti=Ti−1+1. While, the counter block is a true counter, any sequence of Ti can work, but practical considerations may call for more predictable sequences.
While encryption is often used for communications, encryption can also be used for storage. Generally, streaming modes such as CBC, PCBC, CFB and OFB are useful for communications where information is sent in streams, they are not very efficient for storage applications.
FIG. 6A illustrates a typical encrypted storage system. When a storage request is given to controller 602, the content is encrypted by cipher 604. The encrypted content is then stored in storage 606. When a read request is given to controller 602, encrypted content is retrieved from storage 606 and decrypted using cipher 604. In the case of hard disk, it may be more efficient to retrieve large blocks at a time in which case streaming modes could be used across the large block. For example, if 2048-byte blocks are used to store on a hard disk, a CBC mode could be used for a 256-bit (32-byte) block cipher across the 2048 bytes in the hard disk block. However, if storage 606 is memory such as static random access memory (SRAM) or dynamic random access memory (DRAM), where memory is access in a random access fashion, streaming modes are not practical. ECB could be used, but the encryption/decryption operations can introduce unacceptable latency in accessing memory.
FIG. 6B illustrates a data flow in an encrypted memory during a read from memory. An address is supplied to memory 610 which retrieves the ciphertext data. Decryption block 612 is applied to the ciphertext data to retrieve the data in plaintext. If ECB is used, the block cipher operation of ECB must begin after the ciphertext data is retrieved and would not allow for parallel operations and hence would add decryption time to the latency of data retrieval.
FIG. 6C illustrates a data flow into an encrypted memory during a write to memory. Data as plaintext is encrypted by encryption block 614 to produced encoded data as ciphertext which is then stored into memory 610. Typically latency in a write operation is of less concern. In typical memory usage data is written to memory after a processor has need for the information whereas when a processor reads from memory it typically is ready to use it. If a memory is properly buffered, additional latency in write operations due to encryption should not cause a processor to wait more than it would for an unencrypted write.
Encryption of content going into random access memory (RAM) has key applications in point of sale (POS) devices where credit card numbers or account information could be stored which awaiting validation and in digital rights management (DRM) where a movie or song could be received from a transmission, and temporarily stored in memory. Encryption could prevent identity theft in POS devices and prevent unauthorized duplication of copyrighted material. Accordingly, various needs exist in the industry to address the aforementioned deficiencies and inadequacies.